﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FindNthMax
{
    /// <summary>
    /// http://www.careercup.com/question?id=20967663
    /// </summary>
    public static class ArrayExttension
    {
        /// <summary>
        /// In an array of unsorted integers (you may assume the array may contain +ve, -ve and 0s), write a function 
        /// //TODO: Implement the solution using http://en.wikipedia.org/wiki/Quickselect
        /// </summary>
        /// <param name="input"></param>
        /// <returns></returns>
        /// <example>e.g. if this is given array {2, -4, 5, 6, 0, 7, -1, 10, 9} and n=1, it should return the max number, 10 and if n=3, it should return 3rd max number, which is: 7.</example>
        public static int FindNthValue(this int[] input, int nth)
        {
            int max = input[0];
            for (int i = 1; i < input.Length; i++)
            {
                if (input[i] > max)
                    max = input[i];
            }

            if (nth == 1)
                return max;
            else
                return FindMax(input, nth - 1, max);

        }

        public static int FindMax(int[] input, int nth, int max)
        {
            if (nth == 0)
                return max;
            
            int temp = input[0];

            for (int i = 1; i < input.Length; i++)
            {
                int current = input[i];

               if (current > temp && current < max)
                {
                    temp = current;
                }
            }

            return FindMax(input, nth - 1, temp);
        }
        
    }
}
